package com.xinpan.exercise;

public class MaxSubArray {
    public int maxSubArray(int[] A) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(A.length == 1)
            return A[0];
            
        int lMax = subMax(A, 0, A.length/2);
        int rMax = subMax(A, A.length/2, A.length);
        
        int mid = A[A.length/2-1] + A[A.length/2];
        int max = mid;
        int add = max;
        for(int i = A.length/2-2; i >= 0; i--)
        {
            add += A[i];
            if(add > max)
                max = add;
        }
        
        add = max;
        for(int i = A.length/2+1; i < A.length; i++)
        {
            add += A[i];
            if(add > max)
                max = add;
        }
        
        if(lMax < rMax)
            lMax = rMax;
        
        return max > lMax ? max : lMax;
    }
    
    int subMax(int[] A, int s, int e)
    {
        int len = e - s;
        if(len == 0)
            return Integer.MIN_VALUE;
        if(len == 1)
            return A[s];
        
        int m = (s+e)/2;
        int lMax = subMax(A, s, m);
        int rMax = subMax(A, m, e);
        
        int mid = A[m-1] + A[m];
        int max = mid;
        int add = max;
        for(int i = m-2; i >= s; i--)
        {
            add += A[i];
            if(add > max)
                max = add;
        }
        add = max;
        for(int i = m+1; i < e; i++)
        {
            add += A[i];
            if(add > max)
                max = add;
        }
        
        if(lMax < rMax)
            lMax = rMax;
        
        return max > lMax ? max : lMax;
    }
    
    public static void main(String[] args)
    {
    	MaxSubArray msa = new MaxSubArray();
    	
    	int[] A = {0,-1,3,1,-3,2,1,1};
    	msa.maxSubArray(A);
    }
}
